//合并二叉树
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) 
    {
        if(!root1) return root2;
        if(!root2) return root1;
        root1->val+=root2->val;
        root1->left=mergeTrees(root1->left,root2->left);
        root1->right=mergeTrees(root1->right,root2->right);
        return root1;
    }
};
//最大二叉树
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) 
    {
        int left=0;
        int right=nums.size()-1;
        return process(nums,left,right);
    }
    TreeNode* process(vector<int>& nums,int left,int right)
    {
        if(left>right) return nullptr;
        int pos=left;
        int biggest=nums[left];
        for(int i=left+1;i<=right;i++)
        {
            if(nums[i]>biggest)
            {
                pos=i;
                biggest=nums[i];
            }
        }
        TreeNode* root=new TreeNode(biggest);
        root->left=process(nums,left,pos-1);
        root->right=process(nums,pos+1,right);
        return root;
    }
};
//路径总和
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) 
    {
       if(root==nullptr) return false;
       return dfs(root,targetSum-root->val);
    }
    bool dfs(TreeNode* root, int targetSum)
    {
        if(!root->right && !root->left && targetSum==0)
        {
            return true;
        }
        else if(!root->right && !root->left)
        {
            return false;
        }
        if(root->left)
        {
            if(dfs(root->left,targetSum-root->left->val)) return true;
        }
        if(root->right)
        {
            if(dfs(root->right,targetSum-root->right->val)) return true;
        }
        return false;

    }
};